/*
 *  Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
 *  *
 *  This file is part of the Open-source Dependency Toolkit (OSDT),
 *  see http://code.google.com/p/open-source-dependency-toolkit.
 *  
 *  The OSDT is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as 
 *  published by the Free Software Foundation, either version 3 of 
 *  the License, or (at your option) any later version.
 * 
 *  The OSDT is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public 
 *  License along with the OSDT in the files COPYING and COPYING.LESSER.
 *  If not, see http://www.gnu.org/licenses.
 */

package org.osdtsystem.graphs.views;

import org.osdtsystem.exceptions.IllegalCycleException;
import org.osdtsystem.exceptions.EdgeNotFoundException;
import org.osdtsystem.exceptions.FeatureNotFoundException;
import org.osdtsystem.exceptions.LocationNotFoundException;
import org.osdtsystem.exceptions.NodeNotFoundException;
import java.util.List;
import org.osdtsystem.exceptions.IllegalOrderException;
import org.osdtsystem.exceptions.IllegalRelationException;
import org.osdtsystem.values.EdgeID;
import org.osdtsystem.values.Feature;
import org.osdtsystem.values.Layer;
import org.osdtsystem.values.Location;
import org.osdtsystem.values.NodeID;

/**
 * Public interface for an unordered directed tree with edge relation labels. 
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public interface Tree extends View {
    // Construction methods
    /**
     * Add a feature to the list of permitted edge features for the 
     * tree.
     * @param feature the new edge feature
     */
    public void addEdgeFeature(Feature feature);
    
    /**
     * Add a feature to the list of permitted node features for the 
     * tree.
     * @param feature the new node feature
     */
    public void addNodeFeature(Feature feature);
    
    /**
     * Specify the value of a feature at a given location (node or edge).
     * @param location the node or edge
     * @param feature the feature
     * @param value the new feature value at the location
     * @throws LocationNotFoundException
     * @throws FeatureNotFoundException 
     */
    public void setFeatureValue(Location location, Feature feature, Object value)
            throws LocationNotFoundException, FeatureNotFoundException;    
    
    /**
     * Specify the new parent of a given node, and the edge relation. The operation
     * is not performed if it results in a cycle (ie, a non-tree). In this case,
     * an exception is thrown and the tree is left unchanged. If the tree is an ordered tree, 
     * the linear node order must be unchanged by the operation. If the tree is 
     * required to be projective and the method would produce a non-projective order,
     * an exception is thrown and the tree is left unchanged.
     * @param child the child node
     * @param parent the new parent node
     * @param relation the edge relation
     * @return the new edge
     * @throws NodeNotFoundException if one of the nodes is non-existent
     * @throws IllegalCycleException if the operation would result in a cyclic graph
     * @throws IllegalOrderException if the operation would result in an 
     * illegal node ordering
     */
    public EdgeID setParent(NodeID child, NodeID parent, Object relation)
            throws NodeNotFoundException, IllegalCycleException, 
                IllegalOrderException, IllegalRelationException;
    
    /**
     * Add a new child node to the given parent with the given edge relation. 
     * If the tree is an ordered tree, the new node must be added as the last 
     * node in the linear node ordering.
     * @param parent the parent node
     * @param relation the edge relation
     * @return the new node
     * @throws NodeNotFoundException if the parent node is not in the tree
     * @throws IllegalOrderException if the operation would result in an illegal 
     * node ordering
     * @throws IllegalRelationException 
     */
    public NodeID addNode(NodeID parent, Object relation)
            throws NodeNotFoundException, IllegalOrderException, IllegalRelationException;
    
    /**
     * Remove the entire subtree rooted by the given node. Silently ignored
     * if the node does not exist. 
     * @param node the root of the subtree that must be deleted
     */
    public void removeSubtree(NodeID node);
    
    // Query methods
    /**
     * The top node of the entire tree. 
     * @return the top node
     */
    public NodeID top();
    
    /**
     * The edges in the tree (in any order). 
     * @return the list of edges in the tree
     */
    public List<EdgeID> edges();
    
    /**
     * The nodes in the tree (in an unspecified order). 
     * @return the list of nodes
     */
    public List<NodeID> nodes();
    
    /**
     * The parent edge connecting a node with its parent.
     * @param node the node
     * @return the edge from the node's parent to the node
     */
    public EdgeID parentEdge(NodeID node);
    
    /**
     * The child edges connecting a node with its children.
     * @param node the node
     * @return the list of all child edges
     */
    public List<EdgeID> childEdges(NodeID node);
        
    /**
     * True iff <code>dominator</code> is a transitive parent of 
     * <code>dominated</code> in the tree. A node never dominates itself.
     * @param dominator the dominator node
     * @param dominated the dominated node
     * @return <code>true</code> if the domination relation holds, <code>false</code>
     * otherwise.
     */
    public boolean dominates(NodeID dominator, NodeID dominated);
    
   /**
     * The lowest node in the tree that dominates two given nodes 
     * (the <i>lattice join</i>). 
     * @param node1 the first node
     * @param node2 the second node
     * @return the join of the two nodes
     * @throws NodeNotFoundException
     */
    public NodeID join(NodeID node1, NodeID node2) 
            throws NodeNotFoundException;

    
    /**
     * The two paths from <code>node1</code> and <code>node2</code> respectively 
     * to the join of the two nodes in the tree. The path from a node to its join
     * with the other node is empty if the node coincides with the join. 
     * @param node1 the first node
     * @param node2 the second node
     * @return a list containing the two paths from <code>node1</code> and
     * <code>node2</code> respectively to their join.
     * @throws NodeNotFoundException if one of the two nodes doesn't exist in the tree
     */
    public List<List<EdgeID>> joinPaths(NodeID node1, NodeID node2)
            throws NodeNotFoundException;
    
    /**
     * Return the height of the subtree rooted by the given node.
     * The height is defined as the length of the longest directed path
     * from the node to a terminal node in the tree. Height can be defined
     * recursively: if the node is a terminal node, the height is 0; otherwise
     * the height is defined as 1 plus the largest height of any direct child
     * node. 
     * 
     * Implementation note: Having the height of a node is very useful, since it
     * can be used to make many computations a lot more efficient: eg, when
     * calculating domination and joins, or ensuring acyclicity in the tree. 
     * Depth would serve a similar purpose, but is far more expensive to compute
     * in an incremental framework. In a probability model of language, height
     * can be used to penalize structures that are overly non-balanced (in a 
     * balanced tree, every node has a fixed degree and a difference in the 
     * height of siblings of at most 1).
     * @param node the node
     * @return the height of the node
     * @throws NodeNotFoundException if the node is not contained in the tree
     */
    public int height(NodeID node) throws NodeNotFoundException;    
    
    /**
     * The parent node of the given edge. Returns <code>null</code> if the
     * edge is invalid.
     * @param edge the edge
     * @return the parent node
     */
    public NodeID parent(EdgeID edge);

    /**
     * The child node of the given edge. Return <code>null</code> if the
     * edge is invalid.  
     * @param edge the edge
     * @return the child node
     */
    public NodeID child(EdgeID edge);    
    
    /**
     * The relation name associated with the given edge.
     * @param edge the edge
     * @return the relation name
     * @throws EdgeNotFoundException 
     */
    public Object relation(EdgeID edge) throws EdgeNotFoundException;
    
    /**
     * The permitted node features in the tree.
     * @return the list of permitted node features
     */
    public List<Feature> nodeFeatures();
    
    /**
     * The permitted edge features in the tree.
     * @return the list of permitted edge features
     */
    public List<Feature> edgeFeatures();
    
    /**
     * The value of the given feature at the given location (node or edge).
     * @param location the location
     * @param feature the feature
     * @return the value of the feature at the location
     */
    public Object featureValue(Location location, Feature feature);
        
    public boolean containsNode(NodeID node);

    public Layer treeLayer();
}
